package com.clps.algorithm.chapter08.二叉搜索树迭代器;

import com.clps.algorithm.chapter07.二叉树每层的最大值.TreeNode;

import java.util.Stack;

/**
 * 请实现二叉搜索树的迭代器BSTIterator，它主要有如下三个函数：
 *
 * + 构造函数输入一个二叉搜索树的根结点初始化该迭代器；
 * + 函数next返回二叉搜索树中下一个最小的结点的值；
 * + 函数hasNext返回二叉搜索树是否还有下一个结点。
 * 例如输入图8.11中的二叉树搜索树初始化BSTIterator，第一次调用函数next将返回最小的结点值1，此时调用函数hasNext返回true。
 * 再次调用函数next将返回下一个最小的结点的值2，此时再调用函数hasNext将返回true。第三次调用函数next将返回下一个最小的结点的值3，如果此时再调用函数hasNext将返回false。
 */
public class demo01 {

    public static void main(String[] args) {

    }


}

class BstIterator{
    TreeNode cur;
    Stack<TreeNode> stack;

    public BstIterator(TreeNode root) {
        cur = root;
        this.stack = new Stack<>();
    }

    public boolean hasNext(){
        return cur!=null || !stack.isEmpty();
    }
}
